//
// Created by 麻再挺 on 2021/12/13.
//

#include <string.h>
#include "tree_menu.h"
#include "bi_tree.h"
#include "bi_thr_tree.h"
#include "parent_tree.h"
#include "child_tree.h"
#include "huffman_tree.h"

/**
 * 二叉树
 */
void bi_tree();

/**
 * 线索二叉树
 */
void bi_thr_tree();

/**
 * 树的双亲表示法
 */
void pt_tree();

/**
 * 树的孩子表示法
 */
void ct_tree();

/**
 * 哈夫曼树
 */
void ht_tree();

/**
 * 运行主函数
 */
void tree_run() {
    // 菜单
    int menu = -1;
    // 是否运行
    Status is_run = TRUE;
    while (is_run) {
        printf("╔═══════════════════════════════════════════════╗\n");
        printf("║                     树                        ║\n");
        printf("║ 1: 二叉树                                     ║\n");
        printf("║ 2: 线索二叉树                                 ║\n");
        printf("║ 3: 树的双亲表示法                             ║\n");
        printf("║ 4: 树的孩子表示法                             ║\n");
        printf("║ 5: 哈夫曼树                                   ║\n");
        printf("║ 0: 退出                                       ║\n");
        printf("╚═══════════════════════════════════════════════╝\n");
        printf("请选择功能菜单: ");
        scanf("%d", &menu);

        switch (menu) {
            case 0:
                // 退出
                is_run = FALSE;
                break;
            case 1:
                bi_tree();
                break;
            case 2:
                bi_thr_tree();
                break;
            case 3:
                pt_tree();
                break;
            case 4:
                ct_tree();
                break;
            case 5:
                ht_tree();
                break;
            default:
                printf("输入异常\n");
                break;
        }
    }
}


void bi_tree() {
    BiTree t;
    printf("请输入:'-+a  *b  -c  d  /e  f  '\n");
    // '-+a  *b  -c  d  /e  f  '
    CreateBiTree(&t);
    printf("创建二叉树成功\n");
    printf("先序遍历: ");
    PreOrderTraverse(&t);
    printf("\n");
    printf("中序遍历: ");
    InOrderTraverse(&t);
    printf("\n");
    printf("后序遍历: ");
    PostOrderTraverse(&t);
    printf("\n");
    printf("层序遍历: ");
    LevelOrderTraverse(&t);
    printf("\n");
}

/**
 * 线索二叉树
 */
void bi_thr_tree() {
    BiThrTree t;
    printf("请输入:'-+a  *b  -c  d  /e  f  '\n");
    // '-+a  *b  -c  d  /e  f  '
    CreateBiThrTree(&t);
    printf("创建线索二叉树成功\n");
    // 将二叉树按中序线索化
    BiThrTree thrTree;
    InOrderThreading(&thrTree, &t);
    printf("中序遍历: ");
    InOrderThrTraverse(&thrTree);
    printf("\n");
    printf("层序遍历: ");
    LevelOrderThrTraverse(thrTree.lChild);
    printf("\n");
}

void pt_tree() {
    PtTree t;
    PtTree_Init(&t);
    PtTree_Print(&t);
    PtTree_Find_Parent(&t, 'C');
}

void ct_tree() {
    CTree t;
    CTree_Init(&t);
    CTree_Print(&t);
    CTree_Find_Kids(&t, 'C');
}

void ht_tree() {
    // 存储结点权重值的数组
    int w[5] = {2, 8, 7, 6, 5};
    // 长度
    int n = 5;
    HuffmanTree t;
    HuffmanCode code;
    CreateHuffmanTree(&t, w, n);
    PrintHuffmanTree(t, n);
    HuffmanCoding(t, &code, n);
    PrintHuffmanCode(code, w, n);
}